The present invention relates in general to first-in-first-out (FIFO) circuits and, more particularly, to a FIFO operating with a fill level indicator.
Many data processing and communication applications, for example computer networks, require data communication between devices operating asynchronously. One problem with asynchronous communication is that data transmission between data source and data sink must be carefully controlled to prevent loss of data. If the data source transmits information faster than the data sink can accept, information may be lost. Alternately, if the data sink accepts information faster than the data source can provide, the data sink may capture the same data twice. Hence, there must be control over asynchronously transmitted data.
One solution found in the prior art involves handshaking between the data source and data sink. The data source does not send data until the data sink is ready. Likewise, the data sink does not read until the data source indicates that valid data is present. The handshaking procedure tends to slow the communication process and result in inefficient operation because the higher operating speed of the data source or data sink cannot be fully utilized.
Another solution is to insert an asynchronous buffer, e.g. FIFO, between the data source and data sink. The data source may dump data into the buffer at its nominal operating speed. The data sink reads from the buffer at will. The inherent limitation in the buffer approach is its finite length. If the data source is faster than the data sink for some period of time, then the buffer may overflow causing loss of data. If the data sink is faster than the data source, the buffer may become empty and the data sink may read invalid data. Hence, the data source and sink must have feedback from the buffer to help regulate when to enable and disable the flow of data.
Unfortunately, it is difficult to obtain reliable indication of fill status from an asynchronous buffer. If the buffer is implemented as a dual-port RAM with pointers to the first and last location, then a subtractor circuit could compute the difference between the pointers indicating full status of the buffer. However since either pointer can change asynchronously, there is some chance that the data source or data sink will attempt to read the value while it is changing resulting in a significant error.
Hence, a need exists to detect the fill status of an interface buffer between the data source and data sink in a manner that is not subject to serious errors common in asynchronous systems.